#include <iostream>
// #include <ctime>

using namespace std;

const size_t COUNT = 15;

struct Node{
	Node *next;
	Node *randomNext;
};

// Create a single link list
Node* createLinkList(size_t count){
	if(count <= 0)
		return NULL;
	Node *root = new Node();
	root->next = NULL;
	root->randomNext = NULL;

	Node *cur = root;
	for(size_t i = 0; i < count -1; i ++){
		cur->next = new Node();
		cur = cur->next;
		cur->next = NULL;
		cur->randomNext = NULL;
	}

	return root;
}

// Add random link
void createRandomLink(Node *root, size_t count){
	Node *cur = root, *randomNext = root;
	size_t dist = 0, index = 0;
	while(cur != NULL){
		randomNext = root;
		srand(index * 13 + rand());
		cout << "Index: " << index << endl;
		dist = rand() % count;
		index = 0;// Add this morning
		while(index ++ < dist){
			randomNext = randomNext->next;
		}
		cur->randomNext = randomNext;
		cur = cur->next;
	}
}

// Print the list
void printList(Node *list){
	Node *cur = list;
	Node *temp = list;
	int curDist = -1, nextDist = 0, randomNextDist = 0;
	while(cur != NULL){
		curDist ++;
		nextDist = 0;
		randomNextDist = 0;
		
		temp = list;
		while(temp != cur->next){
			nextDist ++;
			temp = temp->next;
		}
		temp = list;
		while(temp != cur->randomNext){
			randomNextDist ++;
			temp = temp->next;
		}
		// cout << "Current Node: " << curDist << ", Next Node: " << nextDist << ", Random Next Node: " << randomNextDist << endl;
		cout << "Current Node: " << cur << ", Next Node: " << cur->next << ", Random Next Node: " << cur->randomNext << endl;
		cur = cur->next;
	}
	cout << endl << endl;
}

// Copy the link list with random link
Node *copyLinkList(Node *linkList){
	if(NULL == linkList)
		return NULL;

	Node *newListRoot = new Node();
	Node *oldCur = linkList, *newCur = newListRoot;
	// Copy the single list
	while(oldCur->next != NULL){
		newCur->next = new Node();
		newCur = newCur->next;
		newCur->randomNext = NULL;
		oldCur =oldCur->next;
	}

	// Copy the random links
	Node *oldTemp = NULL, *newTemp = NULL;
	newCur = newListRoot;
	oldCur = linkList;
	while(oldCur != NULL){
		oldTemp = linkList;
		newTemp = newListRoot;
		while(oldTemp != oldCur->randomNext){
			newTemp = newTemp ->next;
			oldTemp = oldTemp->next;
		}
		newCur->randomNext = newTemp;

		oldCur = oldCur->next;
		newCur = newCur->next;
	}

	return newListRoot;
}

/////////////////////////////////////////////////////////////////
void getLargestNumber(int arr[], const size_t size, int &largest, int &secondLargest){
	if(size <= 0)
		return;
	// int largest = arr[0], secondLargest = arr[0];
	size_t largestIndex = 0, secondLargestIndex = 0;
	for(size_t i = 1; i < size; i ++){
		// Larger than current largest
		if(arr[i] > arr[largestIndex]){
			secondLargestIndex = largestIndex;
			largestIndex = i;
		}
		else if(arr[i] > arr[secondLargestIndex]){ // Larger than current second largest but small than the largest
			secondLargestIndex = i;
		}
	}
	largest = arr[largestIndex];
	secondLargest = arr[secondLargestIndex];
}

int mcmain(int argc, char **argv){
	Node *linkList = createLinkList(COUNT);
	createRandomLink(linkList, COUNT);
	Node *newList = copyLinkList(linkList);

	printList(linkList);
	printList(newList);


	int arr[] = {1213, 21, 2154, 515, 16516163, 16, 5161, 654654, 2, 3, 5};
	int largest = 0, secondLargest =0;

	getLargestNumber(arr, sizeof(arr) / sizeof(int), largest, secondLargest);

	return 0;
}